#include <vector>
#include <string>

using namespace std;

// 198. 打家劫舍
class Solution1
{
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(f[i - 1], g[i - 1] + nums[i]);
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

// 764. 最大加号标志
class Solution2
{
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) 
    {
        vector<vector<int>> grid(n, vector<int>(n, 1));
        for(auto& m : mines) grid[m[0]][m[1]] = 0;

        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n; ++i)
        {
            int count1 = 0, count2 = 0;
            for(int j = 0; j < n; ++j)
            {
                // left
                if(grid[i][j]) ++count1;
                else count1 = 0;
                dp[i][j] = min(dp[i][j], count1);

                // right
                if(grid[i][n - 1 - j]) ++count2;
                else count2 = 0;
                dp[i][n - 1 - j] = min(dp[i][n - 1 - j], count2);
            }
        }

        int ret = 0;
        for(int j = 0; j < n; ++j)
        {
            int count1 = 0, count2 = 0;
            for(int i = 0; i < n; ++i)
            {
                // up
                if(dp[i][j]) ++count1;
                else count1 = 0;
                dp[i][j] = min(dp[i][j], count1);
            }

            for(int i = 0; i < n; ++i)
            {
                // down
                if(dp[n - 1 - i][j]) ++count2;
                else count2 = 0;
                dp[n - 1 - i][j] = min(dp[n - 1 - i][j], count2);

                ret = max(ret, dp[n - 1 - i][j]);
            }
        }

        return ret;
    }
};

// 790. 多米诺和托米诺平铺
class Solution3
{
private:
    const int MOD = 1e9 + 7;

public:
    int numTilings(int n) 
    {
        vector<vector<long long>> dp(n + 1, vector<long long>(4));
        dp[0][3] = 1;
        for(int i = 1; i <= n; ++i)
        {
            dp[i][0] = dp[i - 1][3];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD;
        }

        return dp[n][3];
    }
};

// 有效的数字
class Solution4
{
public:
    bool hasE, hasNum, isFloat; 
    bool isNumber(string& s) 
    {
        for(int i = 0; i < s.size(); i++) 
        {
            auto c = s[i];
            // 符号位只能在首位或E的后一位
            if((c == '-' || c == '+') && (i == 0 || s[i - 1] == 'e' || s[i - 1] == 'E')) 
            {
            }
            else if((c == 'e' || c == 'E') && !hasE && hasNum) 
            {
                //只存在一个E, 前面必须有数字, 后面也必须有数字
                hasE = true;
                hasNum = false;
            }
            else if(c == '.' && !isFloat && !hasE) 
                isFloat = true; //只存在一个小数点, 不能在E的后面
            else if(isdigit(c)) 
                hasNum = true;
            else 
                return false;
        }
        return hasNum;
    }
};